Computing and communication networks typically include network devices, such as routers, firewalls, switches, or gateways, which transfer or switch data, such as packets, from one or more sources to one or more destinations. Network devices may operate on the packets as the packets traverse the network, such as by forwarding or filtering the packet-based network traffic.
In some network devices (e.g., routers), when a child link of an aggregate Ethernet (or synchronous optical networking (SONET) bundle fails, all child nexthops associated with the aggregate Ethernet/SONET bundle need to be re-programmed in a packet forwarding engine (PFE) data plane of the network device. This causes an inordinate amount of PFE data plane writes, which slows convergence of the network device and results in traffic loss.
Load balancing schemes may be implemented (e.g., via PFEs of a network device) for aggregate Ethernet/SONET bundles in order to evenly distribute packets across multiple links of the bundle. In some load balancing schemes, a probability of a packet leaving on a child link (ik) may be represented as pk, and the probabilities (e.g., p1, . . . , pk) may be converted into weights on a scale of “1” to “65535.” For example, the probabilities p1, p2, p3, and p4 are normalized to weights (wk) such that w1+w2+w3+w4=65535. These weights are written along with the child nexthops that represent these child links. A packet hash is compared to each of these weights, and an index at which the packet hash exceeds the programmed weight is chosen to forward a packet. However, in such load balancing schemes, a number of memory reads needed to forward a packet will be proportional to a number of child links in an Ethernet/SONET bundle since the list of weights needs to be scanned to find an appropriate child link.